home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / Hashtable.cpp < prev    next >
Text File  |  1999-07-13  |  7KB  |  330 lines
  1.  
  2. #include "Hashtable.h"
  3.  
  4. #include <stdlib.h>
  5.  
  6.  
  7.  
  8. long Hashtable::sTableSizes[ NUM_SIZES ] = { 23, 97, 397, 797, 3203, 6421, 12853, 51437, 205759, 411527, 1646237, 3292489, 6584983, 13169977, 52679969 };
  9.  
  10. #define _MIN( a, b )    ( (a) > (b) ? (b) : (a) )
  11.     
  12.  
  13. Hashtable::Hashtable( bool inKeysOwned, int inLoadFactor ) {
  14.     mKeysOwned        = inKeysOwned;
  15.     mTableSize        = 0;
  16.     mTable            = NULL;
  17.     mNumEntries        = 0;
  18.     mThreshold        = 0;
  19.     mLoadFactor        = inLoadFactor;
  20.     
  21.     // Don't let the client kill himself with a bad load factor
  22.     if ( mLoadFactor > 100 )
  23.         mLoadFactor = 100;
  24.     else if ( mLoadFactor < 10 )
  25.         mLoadFactor = 10;
  26.         
  27.     Rehash();
  28. }
  29.  
  30.  
  31. Hashtable::~Hashtable() {
  32.     RemoveAll();
  33.     
  34.     if ( mTable )
  35.         delete []mTable;
  36. }
  37.  
  38.     
  39. void Hashtable::Rehash() {
  40.     long        i, index, oldSize = mTableSize;
  41.     KEntry*        temp, *entry;
  42.     KEntry**    oldTable = mTable;
  43.     
  44.     // Find the next bigger table size
  45.     for ( i = 0; mTableSize <= oldSize; i++ )
  46.         mTableSize = sTableSizes[ i ];
  47.  
  48.     
  49.     // Alloc the new table and make it empty    
  50.     mTable = new KEntry*[ mTableSize ];
  51.     for ( i = 0; i < mTableSize; i++ )
  52.         mTable[ i ] = NULL;
  53.     
  54.     // Rehash all the old values into the new table
  55.     for ( i = 0; i < oldSize; i++ ) {
  56.         for ( entry = oldTable[ i ]; entry; ) {
  57.             index = entry -> mKey % mTableSize;
  58.             temp = entry -> mNext;
  59.             entry -> mNext = mTable[ index ];
  60.             mTable[ index ]    = entry;
  61.             entry = temp;
  62.         }    
  63.     }
  64.  
  65.     // Set the new size thet we'll rehash at
  66.     mThreshold = mLoadFactor * mTableSize / 100;
  67.     
  68.     // We don't need the old table anymore
  69.     if ( oldTable )
  70.         delete []oldTable;
  71. }
  72.  
  73.  
  74.  
  75.  
  76.  
  77. void* Hashtable::put( long inKey, const Hashable* inHKey, void* inValue ) {
  78.     long        index;
  79.     KEntry*        entry;
  80.     void*        oldVal;
  81.  
  82.     // See if we need to make the hash table bigger
  83.     if ( mNumEntries >= mThreshold )
  84.         Rehash();
  85.     
  86.     // If we already have the key, replace the value and pass the old one back
  87.     entry = fetchEntry( inKey, inHKey );
  88.     if ( entry ) {
  89.         oldVal            = entry -> mValue;
  90.         if ( mKeysOwned && inHKey )
  91.             delete inHKey; }
  92.     else { 
  93.         oldVal                = NULL;
  94.         index                = ((unsigned long) inKey) % mTableSize;
  95.         entry                = new KEntry;
  96.         entry -> mHashable    = inHKey;
  97.         entry -> mKey        = ((unsigned long) inKey);
  98.         entry -> mNext        = mTable[ index ];
  99.         mTable[ index ]        = entry;
  100.         mNumEntries++;
  101.     }
  102.     
  103.     entry -> mValue        = inValue;
  104.     
  105.     return oldVal;
  106. }
  107.  
  108.  
  109.  
  110. bool Hashtable::Get( long inKey, void** outValue ) const {
  111.     KEntry*    entry = fetchEntry( inKey, NULL );
  112.  
  113.     if ( entry && outValue ) 
  114.         *outValue = entry -> mValue;
  115.  
  116.     return entry != NULL;
  117. }
  118.  
  119.  
  120. bool Hashtable::Get( const Hashable* inKey, void** outValue ) const {
  121.     KEntry*    entry = fetchEntry( inKey -> Hash(), inKey );
  122.  
  123.     if ( entry && outValue ) 
  124.         *outValue = entry -> mValue;
  125.  
  126.     return entry != NULL;
  127. }
  128.  
  129.  
  130.  
  131. void Hashtable::GetValues( XPtrList& outValues ) {
  132.     KEntry** entryP = mTable, *entry;
  133.     int i;
  134.     
  135.     outValues.RemoveAll();
  136.     outValues.Dim( 4 );
  137.     
  138.     for ( i = 0; i < mTableSize; i++ ) {
  139.         entry = *entryP;
  140.         while ( entry ) {
  141.             outValues.Add( entry -> mValue );
  142.             entry = entry -> mNext;
  143.         }
  144.  
  145.         entryP++;
  146.     }
  147. }
  148.  
  149.  
  150. void Hashtable::GetKeys( XPtrList& outKeys ) {
  151.     KEntry** entryP = mTable, *entry;
  152.     int i;
  153.     
  154.     outKeys.RemoveAll();
  155.     outKeys.Dim( 4 * NumEntries() );
  156.     
  157.     for ( i = 0; i < mTableSize; i++ ) {
  158.         entry = *entryP;
  159.         while ( entry ) {
  160.             outKeys.Add( ( entry -> mHashable ) ? entry -> mHashable : (void*) entry -> mKey );
  161.             entry = entry -> mNext;
  162.         }
  163.  
  164.         entryP++;
  165.     }
  166. }
  167.  
  168.  
  169.  
  170.  
  171. KEntry*    Hashtable::fetchEntry( long inKey, const Hashable* inHKey ) const {
  172.     long        index = ( (unsigned long) inKey ) % mTableSize;
  173.     KEntry*        entry = mTable[ index ];
  174.  
  175.     // Look thru the chain for the key and the entry holding that key-value pair
  176.     while ( entry ) {
  177.         if ( entry -> mKey == inKey ) {
  178.             if ( ! entry -> mHashable || ! inHKey )
  179.                 return entry;
  180.             else if ( inHKey -> Equals( entry -> mHashable ) )
  181.                 return entry;
  182.         }
  183.         entry = entry -> mNext;
  184.     }
  185.     
  186.     return NULL;
  187. }
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194. void Hashtable::RemoveAll() {
  195.     long i;
  196.     KEntry*    entry, *temp;
  197.     
  198.     // Step theu the dict table and delete all the KEntries
  199.     for ( i = 0; i < mTableSize; i++ ) {
  200.         for ( entry = mTable[ i ]; entry; ) {
  201.             if ( mKeysOwned && entry -> mHashable )
  202.                 delete entry -> mHashable;
  203.             temp = entry -> mNext;
  204.             delete entry;
  205.             entry = temp;
  206.         }
  207.         mTable[ i ] = NULL;
  208.     }
  209.     mNumEntries = 0;
  210. }
  211.  
  212.  
  213.  
  214. void* Hashtable::remove( long inKey, const Hashable* inHKey ) {
  215.     long        index = ( (unsigned long) inKey ) % mTableSize;
  216.     KEntry*        entry = mTable[ index ], *prev = NULL;
  217.     bool        isEqual;
  218.     void*        retVal;
  219.  
  220.     // Look thru the chain for a matching key and delete it
  221.     while ( entry ) {
  222.         if ( entry -> mKey == inKey ) {
  223.             if ( inHKey && entry -> mHashable )
  224.                 isEqual = inHKey -> Equals( entry -> mHashable );
  225.             else
  226.                 isEqual = true;
  227.                 
  228.             if ( isEqual ) {
  229.                 if ( mKeysOwned && entry -> mHashable )
  230.                     delete entry -> mHashable;
  231.  
  232.                 if ( prev == NULL ) 
  233.                     mTable[ index ] = NULL;
  234.                 else 
  235.                     prev -> mNext = entry -> mNext;
  236.                 retVal = entry -> mValue;
  237.                 delete entry;
  238.                 mNumEntries--;
  239.                 return retVal;
  240.             }
  241.         }
  242.         prev = entry;
  243.         entry = entry -> mNext;
  244.     }
  245.     
  246.     return NULL;
  247. }
  248.  
  249.  
  250.  
  251. long& Hashtable::operator[] ( const long inKey ) {
  252.     KEntry*    entry = fetchEntry( inKey, NULL );
  253.     
  254.     if ( ! entry ) {
  255.         Put( inKey, 0 );
  256.         entry = fetchEntry( inKey, NULL );
  257.     }
  258.     
  259.     return (long&) entry -> mValue;
  260. }
  261.  
  262.  
  263.  
  264. void*& Hashtable::operator[] ( const void* inKey ) {
  265.     KEntry*    entry = fetchEntry( (long) inKey, NULL );
  266.     
  267.     if ( ! entry ) {
  268.         Put( (long) inKey, 0 );
  269.         entry = fetchEntry( (long) inKey, NULL );
  270.     }
  271.     
  272.     return entry -> mValue;
  273. }
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280. void Hashtable::Rank( XPtrList& outKeys, CompFunctionT inCompFcn, long inNumToRank ) {
  281.     long i, n = NumEntries();
  282.     KEntry** entryP = mTable, *entry;
  283.     const void **p, **temp = new void*[ 2 * n ];
  284.     
  285.     if ( inNumToRank < 0 )
  286.         inNumToRank = n;
  287.     inNumToRank = _MIN( inNumToRank, n );
  288.  
  289.     // To rank, we must sort by value, with a tag on each element of its key
  290.     p = temp;
  291.     for ( i = 0; i < mTableSize; i++ ) {
  292.         entry = *entryP;
  293.         while ( entry ) {
  294.             *p = entry -> mValue;  
  295.             p++; 
  296.             *p = ( entry -> mHashable ) ? entry -> mHashable : (const void*) entry -> mKey;
  297.             p++;
  298.             entry = entry -> mNext;
  299.         }
  300.  
  301.         entryP++;
  302.     }
  303.  
  304.     // Default to long-long ranking
  305.     if ( ! inCompFcn )
  306.         inCompFcn = sLongComparitor;
  307.     
  308.     // Sort the floats
  309.     qsort( temp, n, 8, inCompFcn );
  310.     
  311.     // Put the sorted results in the destination
  312.     outKeys.RemoveAll();
  313.     p = temp + 1;
  314.     for ( i = 0; i < n; i++ ) {
  315.         outKeys.Add( *p );
  316.         p += 2;
  317.     }
  318.     
  319.     // Cleanup
  320.     delete []temp;
  321. }
  322.  
  323.  
  324.  
  325.  
  326.  
  327. int Hashtable::sLongComparitor( const void* inA, const void* inB ) {
  328.     return ((long) inB - (long) inA);
  329. }
  330.